#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* head = new ListNode(-1);
    auto tail = head;
    while (true)
    {
        int pos = -1;
        for (int i = 0; i < lists.size(); i++)
        {
            if (pos == -1 && lists[i])
                pos = i;
            else if (pos != -1 && lists[i] && lists[i]->val < lists[pos]->val)
                pos = i;
        }
        if (pos == -1)   break;
        tail->next = lists[pos];
        tail = tail->next;
        lists[pos] = lists[pos]->next;
    }
    return head->next;
}

struct Status {
    int val;
    ListNode* ptr;
    bool operator < (const Status& rhs) const {
        return val > rhs.val;
    }
};

priority_queue <Status> q;

ListNode* mergeKLists(vector<ListNode*>& lists) {
    for (auto node : lists) {
        if (node) q.push({ node->val, node });
    }
    ListNode head, * tail = &head;
    while (!q.empty()) {
        auto f = q.top(); q.pop();
        tail->next = f.ptr;
        tail = tail->next;
        if (f.ptr->next) q.push({ f.ptr->next->val, f.ptr->next });
    }
    return head.next;
}